Основне статистике (збир, производ, просек, минумум, максимум)
Најчешће коришћени итеративни алгоритми служе за израчунавање статистика бројевних серија. На пример, једну такву серију могу чинити бројеви 1, 2, 3, 4 и 5. Најзначајније статистике су:
- збир елемената (збир бројева из примера је 15),
- производ елемената (производ бројева из примера је 120),
- минимум тј. најмањи од свих елемената (миминум бројева из примера је 1),
- максимум тј. највећи од свих елемената (максимум бројева из примера је 5).
Одређивање збира и производа
На примеру четворочлане серије елемената, прикажимо итеративне алгоритме за одређивање збира и производа. Збир четири броја се најједноставније израчунава изразом
+ broj2 + broj3 + broj4 broj1
што је због леве асоцијативности сабирања (у програмирању) идентично изразу
((broj1 + broj2) + broj3) + broj4
Други начин да се израчунавање збира реализује је да се уведе помоћна
променљива zbir
која би се увећавала за текући елемент.
= broj1;
zbir = zbir + broj2;
zbir = zbir + broj3;
zbir ...
За разлику од полазног решења у ком се збир израчунава само помоћу
једног израза, ово решење је итеративно, и резултат се добија
узастопном применом корака истог облика. Истакнимо још једном врло важну
особину итеративних алгоритама, а то је да се током њиховог извршавања
мења вредност неке променљиве (у овом случају то је променљива
zbir
).
Уместо да збир иницијализујемо првим елементом, можемо га иницијализовати нулом, а затим увећавати за један по један елемент.
= 0;
zbir = zbir + broj1;
zbir = zbir + broj2;
zbir ...
Производ се одређује по веома сличном принципу, осим што уместо иницијализације нулом користимо иницијализацију јединицом (као неутралним елементом за множење) и што уместо сабирања користимо множење.
= 1;
proizvod = proizvod * broj1;
proizvod = proizvod * broj2;
proizvod ...
У задацима је често потребно израчунати просек тј. аритметичку средину серије елемената, која је једнака количнику збира и броја елемената.
Одређивање минимума и максимума
Потпуно аналогно израчунавању збира неколико бројева, може се израчунати минимум, једино што се уместо операције сабирања два броја користи операција одређивања минимума два броја. У сваком кораку се рачуна минимум минимума свих претходних бројева и текућег броја.
Реално је претпоставити да на располагању имамо функцију којом се
израчунава минимум два броја. Таква функција је обично део стандардне
библиотеке, а када није, једноставно се може дефинисати.
У језику Пајтон минимум два броја може се израчунати
библиотечком функцијом min
. Минимум
четири броја онда можемо одредити наредним изразом.
min(min(min(broj1, broj2), broj3), broj4)
Максимум израчунавамо по потпуно истом принципу, једино што уместо минимума два броја у сваком кораку користимо максимум два броја.
И у случају налажења минимума уместо једног израза можемо дефинисати и итеративни алгоритам.
= broj1
minimum = min(minimum, broj2)
minimum = min(minimum, broj3)
minimum ...
Ако би се уместо функције за рачунање минимума два броја употребило гранање (овај пут изражено условним изразом), дошло би се до следећег кода.
= broj1
minimum = broj2 if broj2 < minimum else minimum
minimum = broj3 if broj3 < minimum else minimum
minimum ...
Ако би се уместо условног израза користила наредба гранања, добио би се следећи облик кода.
= broj1
minimum if broj2 < minimum:
= broj2
minimum else:
= minimum
minimum if broj3 < minimum:
= broj3
minimum else:
= minimum
minimum ...
Јасно је да гране else
немају никакав ефекат и могу се
изоставити. Тиме добијамо уобичајени алгоритам одређивања минимума.
= broj1
minimum if broj2 < minimum:
= broj2
minimum if broj3 < minimum:
= broj3
minimum ...
Дакле, променљиву minimum
иницијализујемо вредношћу
првог броја, а затим је редом поредимо са другим, трећим, четвртим и
петим бројем и када год је неки од тих бројева мањи од дотадашње
вредности минимума тј. вредности променљиве minimum
,
ажурирмо вредност те променљиве и постављамо је на број за који смо
открили да је мањи од ње.
Можемо и мало прецизније да анализирамо претходни кôд и да докажемо
његову коректност. У првом кораку вредност променљиве
minimum
биће минимум једночланог скупа
{broj1}
, у другом биће минимум двочланог скупа
{broj1, broj2}
, након трећег биће минимум скупа
{broj1, broj2, broj3}
и тако даље. Такав услов, дакле, важи
у сваком кораку нашег програма и назива се инваријанта. Ако је,
на пример, вредност променљиве minumum
вредност минимума
скупа {broj1, broj2, broj3}
и ако је broj4
мањи од вредности те променљиве, тада је broj4
мањи од
најмање вредности у скупу {broj1, broj2, broj3}
, што значи
да је мањи од свих вредности тог скупа и да је минимум скупа
{broj1, broj2, broj3, broj4}
управо broj4
.
Пошто се вредност променљиве minimum
ажурира на вредност
broj4
одржава се услов да је вредност променљиве
minimum
управо минимум скупа
{broj1, broj2, broj3, broj4}
, тј. инваријанта је одржана.
Са друге стране, ако услов не важи, то значи да је најмањи од бројева из
скупа {broj1, broj2, broj3}
мањи или једнак вредности
broj4
и то је уједно минимум скупа
{broj1, broj2, broj3, broj4}
. Пошто се вредност променљиве
minimum
не мења, инваријанта је опет одржана.
Као што се збир може иницијализовати нулом, а производ јединицом, што
су неутралне вредности за сабирање тј. множење, тако се и минимум може
иницијализовати вредношћу \(+\infty\),
а максимум вредношћу \(-\infty\).
У програмском језику Пајтон целобројни тип је
неограничен, међутим, већина задатака у збирци је таква да се може
радити и у другим језицима у којима постоје ограничења вредности
целобројних типова. У језику Пајтон уместо вредности \(+\infty\) можемо употребити вредност
sys.maxsize
(која је обично једнака \(2^{63}-1\)), јер су задаци такви да се у
њима не јављају бројеви већи од тога. Слично, уместо вредности \(-\infty\) се може користити
-sys.maxsize-1
(која је обично једнака \(-2^{63}\)), јер је то најмањи број који се
у другим језицима може представити уграђеним целобројним типовима
података.
Рецимо и да се понављање кода може избећи ако би се употребила петља, што ћемо примењивати када будемо радили са дужим серијама елемената. Сви принципи алгоритма су исти и зато рад са малим серијама бројева представља одличан увод за рад са дужим серијама и петљама.
Низови и библиотечке функције
Уместо ручне имплементације одређивања минимума четири променљиве, можемо употребити низ и библиотечке функције за одређивање максимума низа. О разним врстама низова биће речи у поглављу о низовима, а до тада ћемо разматрати само низове који садрже мали број елемената и који су иницијализовани директним набрајањем њихових елемената.
У језику Пајтон низ који садржи пет бројева се може дефинисати на следећи начин.
= [broj1, broj2, broj3, broj4, broj5] a
Овакав низ се у Пајтону зове листа, а приликом набрајања елемената они се наводе у угластим заградаима. Могуће је у старту формирати празну листу, а касније додавати један по један елемент на ту листу.
= []
a int(input()))
a.append(int(input()))
a.append( ...
Приметимо да бројање позиција елемената низа почиње увек од нуле!
Када је низ дефинисан, број, збир, минимум и максимум његових
елемената можемо веома једноставно да одредимо редом помоћу функција
len
, sum
, min
и max
које су уграђене у сам језик Пајтон.
...= len(a) # odredjuje broj elemenata niza a
n = sum(a) # odredjuje zbir svih elemenata niza a
zbir = min(a) # odredjuje minimum svih elemenata niza a
minimum = max(a) # odredjuje maksimum svih elemenata niza a maksimum
У Пајтону функцијама min
и max
можемо да
проследимо додатни параметар key=f
, где је f
нека функција. Код тако задатог позива функције min
, не
тражимо елемент x
низа a
који је најмањи, него
онај за који је f(x)
најмање. Слично важи и за функцију
max
.